#include "../BST/BST.hpp"

template <class T>
class Splay: public BST<T>
{
protected:
	/**
	 * @brief extend the node v to the root.
	 * 
	 */
	BinNodePosi(T) splay(BinNodePosi(T) v);
public:
	BinNodePosi(T) &search(T const &e);
	BinNodePosi(T) insert(T const &e);
	bool remove(T const &e);
};

/* establish a father-son relationship */
template <class NodePosi> inline
void attachAsLChild(NodePosi p, NodePosi lc) {
	p->lc = lc;
	if(lc) lc->parent = p;
}

/* establish a father-son relationship */
template <class NodePosi> inline
void attachAsRChild(NodePosi p, NodePosi rc) {
	p->rc = rc;
	if(rc) rc->parent = p;
}

template <class T>
BinNodePosi(T) Splay<T>::splay(BinNodePosi(T) v) {
	if(!v) return nullptr;

	BinNodePosi(T) p;
	BinNodePosi(T) g;

	/* double spiral */
	/* rotate from the bottom up. */
	while((p = v->parent) && (g = p->parent)) {
		BinNodePosi(T) gg = g->parent;
		if(IsLChild(*v)) {
			if(IsLChild(*p)) {
				attachAsLChild(g, p->rc);
				attachAsLChild(p, v->rc);

				attachAsRChild(p, g);
				attachAsRChild(v, p);
			}
			else {
				attachAsLChild(p, v->rc);
				attachAsLChild(g, v->lc);

				attachAsLChild(v, g);
				attachAsLChild(v, p);
			}
		}
		else if(IsRChild(*p)) {
			attachAsRChild(g, p->lc);
			attachAsRChild(p, v->lc);

			attachAsLChild(p, g);
			attachAsLChild(v, p);
		}
		else {
			attachAsRChild(p, v->lc);
			attachAsLChild(g, v->rc);

			attachAsRChild(v, g);
			attachAsLChild(v, p);
		}

		/* single spiral */
		if(!gg) v->parent = NULL;
		else {
			(g == gg->lc) ? attachAsLChild(gg, v) : attachAsRChild(gg, v);
		}

		this->updateHeight(g);
		this->updateHeight(p);
		this->updateHeight(v);
		
	}

	p = v->parent;
	if(p) {
		if(IsLChild(*v)) {
			attachAsLChild(p, v->rc);
			attachAsRChild(v, p);
		}
		else {
			attachAsRChild(p, v->lc);
			attachAsLChild(v, p);
		}
		this->updateHeight(p);
		this->updateHeight(v);
		
	}

	v->parent = NULL;
	return v;
}


template <typename T>
BinNodePosi(T) Splay<T>::insert(T const &e) {
	if(!this->_root) {
		this->_root = new BinNode<T>(e);
		++this->_size;
		return this->_root;
	}

	if(e == this->search(e)->data) {
		return this->_this->root;
	}

	/* t->data is closed to e after search operation with splay */
	this->_size++;
	BinNodePosi(T) t = this->_root;
	if(this->_root->data < e) {
		t->parent = this->_root = new BinNode<T>(e, NULL, t, t->rc);
		if(HasRChild(*t)) {
			t->rc->parent = this->_root;
			t->rc = NULL;
		}
	}
	else {
		t->parent = this->_root = new BinNode<T>(e, NULL, t->lc, t);
		if(HasLChild(*t)) {
			t->lc->parent = this->_root;
			t->lc = NULL;
		}
	}
	this->updateHeightAbove(t);
	return this->_root;
}

template <typename T>
BinNodePosi(T) & Splay<T>::search(T const &e) {
	/* _hot->data is the most closed to e */
	BinNodePosi(T) p = searchIn(this->_root, e, this->_hot = NULL);
	this->_root = splay(p ? p : _hot);
	return this->_root;
}
template <typename T>
bool Splay<T>::remove(T const &e) {
	if(!this->_root || (e != search(e)->data)) {
		return false;
	}

	BinNodePosi(T) w =  this->_root;
	/* there is no left subtree. */
	if(!HasLChild(*this->_root)) {
		this->_root = this->_root->rc;
		if(this->_root) {
			this->_root->parent = NULL;
		} 
	}
	/* there is no right subtree. */
	else if(!HasRChild(*this->_root)) {
		this->_root = this->_root->lc;
		if(this->_root) {
			this->_root->parent = NULL;
		}
	}
	else {
		/* secede the left subtree "lTree". */
		BinNodePosi(T) lTree = this->_root->lc;
		lTree->parent = NULL;
		this->_root->lc = NULL;

		this->_root = this->_root->rc;
		this->_root->parent = NULL;

		/* Do a fail-safe lookup 
		 * so that the smallest node 
		 * in the right subtree extends to the root.  
		 * And the root node must have no left subtree after this lookup.
		 * */
		search(w->data);
		this->_root->lc = lTree;
		lTree->parent = this->_root;
	}
	release(w->data);
	release(w);
	this->_size--;

	if(this->_root) {
		this->updateHeight(_root);
	}

	return true;
}